package BF;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Test {
    //汉诺塔问题
    public static void func(int i ,String start,String end,String other){
        if (i == 1){
            System.out.println("Move 1 from "+start+"to"+end);
        }else {
            func(i-1,start,other,end);
            System.out.println("Move "+i+"from"+start+"to"+"end");
            func(i-1,other,end,start);
        }
    }
    //打印该字符串的所有的子集
    //当前来到i位置, 要和不要,走俩条路
    //res是之前的选择所形成的列表
    public static void process1(char[] str, int i, List<Character> res){
        if (i == str.length){
            System.out.println(res.toString());
            return;
        }
        List<Character> resKeep = copyList(res);
        //将res复制一份给resKeep;
        resKeep.add(str[i]);
        process1(str,i+1,resKeep);//要当前字符的路
        List<Character> resNoInclude = copyList(res);
        process1(str,i+1,resNoInclude);//不要当前字符的路
    }
    public static List<Character> copyList(List<Character> res){
        return null;
    }
    //改进后的字符的子集
    //省空间,但是时间复杂度一样的
    public static void process2(char[] str, int i){
        if (i == str.length){
            System.out.println(String.copyValueOf(str));
            return;
        }
        process2(str,i+1);//要当前字符的路
        char tmp =str[i];
        str[i] =0;
        process2(str,i+1);//不要当前字符的路
        str[i] = tmp;
    }
    /*打印字符串的全排列
    * str[i..]范围伤,所有的字符,都可以在i位置上,后续都去尝试
    * str[0...i-1]范围上,是之前做的选择,将所有的字符串形成的全排列加到ArrayList中*/
    /*去掉重复就是将注释掉的代码块加上*/
    public static void proces(char[] str , int i, ArrayList<String> res){
        if (i == str.length){
            res.add(String.valueOf(str));//结果集
        }
        boolean[] visit = new boolean[26];
        for (int j = i; j < str.length; j++) {
           // if (!visit[str[j] - 'a']){
                /*如果这个字符试过了,我就不让它在进来了,(剪枝思想,常数项优化)
                * 当然也可以得到全排列然后去去重*/
             //   visit[str[j] - 'a'] = true;
                swap(str,i,j);//然后续来到i位置去遍历
                proces(str,i+1,res);
                swap(str,i,j);//然后在交换回来
            //}
        }
    }
    public static void swap(char[] chars,int i,int j){
        char tmp =chars[i];
        chars[i] =chars[j];
        chars[j] = tmp;
    }

    /*栈问题 - 逆序栈 ,不能申请额外的数据结构*/
    public static void reverse(Stack<Integer> stack){
        if (stack.isEmpty()){
            return;
        }
        int i =f(stack);
        reverse(stack);
        stack.push(i);
    }
    public static int f(Stack<Integer> stack){
        int result = stack.pop();
        if (stack.isEmpty()){
            return result;
        }else {
            int last = f(stack);
            stack.push(result);
            return last;
        }
    }
    /*对应问题 - ??? */
    public static int process(char[] str ,int i){
        if (i == str.length){
            return 1;
        }
        if (str[i] == '0'){
            return  0;
        }
        if (str[i] == '1'){
            int res = process(str,i+1);
            if (i+1 < str.length){
                res += process(str,i+2);
            }
        }
        if (str[i] == '2'){
            int res = process(str,i+1);
            if (i + 1 < str.length &&(str[i+1] >= '0' && str[i+1] <= '6')){
                res +=process(str,i+2);
            }
            return res;
        }
        return process(str,i+1);
    }
    /*挑选货物 - 给定你一些货物和重量 ,在你的最大承重范围内,你能挑选的最有价值的是多大*/
    public static int process3(int[] weights , int[] values,
                               int i , int alreadyweight,int bag){
        if (alreadyweight > bag)return 0;
        if (i == weights.length)return 0;

        return Math.max(
                process3(weights,values,i+1,alreadyweight,bag),
                values[i]+process3
                        (weights,values,i+1,weights[i]+alreadyweight,bag));
    }

    public  static List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int val:nums) {
            modify(val,nums);
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i+1){
                list.add(i+1);
            }
        }
        return list;
    }
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int val:nums) {
            modify(val,nums);
        }
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] - 1 != i) {
                list.add(nums[i]);
            }
        }
        return list;
    }
    private static void modify(int val, int[] arr) {
        while (arr[val-1] != val){
            int tmp = arr[val-1];
            arr[val-1] = val;
            val =tmp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {4,3,2,7,8,2,3,1};
        findDisappearedNumbers(arr);
    }

}
